
class Node:
    """
    Node represents a node in a binary search tree.

    Attributes:
        data: Data stored in the node.
        left: Left child node.
        right: Right child node.
    """

    def __init__(self, data):
        """
        Initialize a Node with data and empty left and right child nodes.

        Args:
            data: Data for this node.
        """
        self.data = data
        self.left = None
        self.right = None

    def __repr__(self):
        """
        Returns a string representation of the node.

        Returns:
            String representation of the node.
        """
        return f"Node({self.data})"


class BinarySearchTree:
    """
    BinarySearchTree represents a binary search tree data structure.

    Attributes:
        root: Root node of the binary search tree.
    """

    def __init__(self):
        """
        Initialize an empty binary search tree with no root node.
        """
        self.root = None

    def __repr__(self):
        """
        Returns a string representation of the BinarySearchTree.

        Returns:
            String representation of the BinarySearchTree.
        """
        return f"BinarySearchTree(size={self.size()}, height={self.height()}, root={self.root})"

    def __str__(self):
        """
        Returns a string representing the BinarySearchTree.

        Returns:
            String representing the BinarySearchTree.
        """
        return self._display()

    def insert(self, data):
        """
        Inserts a node with the given data into the binary search tree.

        Args:
            data: Data to be inserted into the binary search tree.
        """
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert_recursive(data, self.root)

    def _insert_recursive(self, data, current_node):
        """
        Recursive helper method to insert a node with the given data into the binary search tree.

        Args:
            data: Data to be inserted into the binary search tree.
            current_node: Current node being visited.
        """
        if data < current_node.data:
            if current_node.left is None:
                current_node.left = Node(data)
            else:
                self._insert_recursive(data, current_node.left)
        else:
            if current_node.right is None:
                current_node.right = Node(data)
            else:
                self._insert_recursive(data, current_node.right)

    def search(self, data):
        """
        Searches for a node with the given data in the binary search tree.

        Args:
            data: Data to search for in the binary search tree.

        Returns:
            True if the node is found, False otherwise.
        """
        return self._search_recursive(data, self.root)

    def _search_recursive(self, data, current_node):
        """
        Recursive helper method to search for a node with the given data in the binary search tree.

        Args:
            data: Data to search for in the binary search tree.
            current_node: Current node being visited.

        Returns:
            True if the node is found, False otherwise.
        """
        if current_node is None:
            return False
        if data == current_node.data:
            return True
        elif data < current_node.data:
            return self._search_recursive(data, current_node.left)
        else:
            return self._search_recursive(data, current_node.right)

    def delete(self, data):
        """
        Deletes a node with the given data from the binary search tree.

        Args:
            data: Data to be deleted from the binary search tree.
        """
        self.root = self._delete_recursive(data, self.root)

    def _delete_recursive(self, data, current_node):
        """
        Recursive helper method to delete a node with the given data from the binary search tree.

        Args:
            data: Data to be deleted from the binary search tree.
            current_node: Current node being visited.

        Returns:
            The updated root node after deletion.
        """
        if current_node is None:
            return current_node

        if data < current_node.data:
            current_node.left = self._delete_recursive(data, current_node.left)
        elif data > current_node.data:
            current_node.right = self._delete_recursive(data, current_node.right)
        else:
            if current_node.left is None and current_node.right is None:
                current_node = None
            elif current_node.left is None:
                current_node = current_node.right
            elif current_node.right is None:
                current_node = current_node.left
            else:
                min_node = self._find_min(current_node.right)
                current_node.data = min_node.data
                current_node.right = self._delete_recursive(min_node.data, current_node.right)

        return current_node

    def _find_min(self, current_node):
        """
        Finds the minimum node in the binary search tree.

        Args:
            current_node: Current node being visited.

        Returns:
            The minimum node.
        """
        while current_node.left is not None:
            current_node = current_node.left
        return current_node

    def size(self):
        """
        Calculates the size (number of nodes) of the binary search tree.

        Returns:
            Size of the binary search tree.
        """
        return self._size_recursive(self.root)

    def _size_recursive(self, current_node):
        """
        Recursive helper method to calculate the size of the binary search tree.

        Args:
            current_node: Current node being visited.

        Returns:
            Size of the subtree rooted at the current node.
        """
        if current_node is None:
            return 0
        return 1 + self._size_recursive(current_node.left) + self._size_recursive(current_node.right)

    def height(self):
        """
        Calculates the height of the binary search tree.

        Returns:
            Height of the binary search tree.
        """
        return self._height_recursive(self.root)

    def _height_recursive(self, current_node):
        """
        Recursive helper method to calculate the height of the binary search tree.

        Args:
            current_node: Current node being visited.

        Returns:
            Height of the subtree rooted at the current node.
        """
        if current_node is None:
            return -1
        return 1 + max(self._height_recursive(current_node.left), self._height_recursive(current_node.right))

    def in_order_traversal(self):
        """
        Performs in-order traversal of the binary search tree.

        Returns:
            List of nodes traversed in in-order order.
        """
        result = []
        self._in_order_traversal_recursive(self.root, result)
        return result

    def _in_order_traversal_recursive(self, current_node, result):
        """
        Recursive helper method to perform in-order traversal of the binary search tree.

        Args:
            current_node: Current node being visited.
            result: List to store the nodes in in-order order.
        """
        if current_node is not None:
            self._in_order_traversal_recursive(current_node.left, result)
            result.append(current_node.data)
            self._in_order_traversal_recursive(current_node.right, result)

    def pre_order_traversal(self):
        """
        Performs pre-order traversal of the binary search tree.

        Returns:
            List of nodes traversed in pre-order order.
        """
        result = []
        self._pre_order_traversal_recursive(self.root, result)
        return result

    def _pre_order_traversal_recursive(self, current_node, result):
        """
        Recursive helper method to perform pre-order traversal of the binary search tree.

        Args:
            current_node: Current node being visited.
            result: List to store the nodes in pre-order order.
        """
        if current_node is not None:
            result.append(current_node.data)
            self._pre_order_traversal_recursive(current_node.left, result)
            self._pre_order_traversal_recursive(current_node.right, result)

    def post_order_traversal(self):
        """
        Performs post-order traversal of the binary search tree.

        Returns:
            List of nodes traversed in post-order order.
        """
        result = []
        self._post_order_traversal_recursive(self.root, result)
        return result

    def _post_order_traversal_recursive(self, current_node, result):
        """
        Recursive helper method to perform post-order traversal of the binary search tree.

        Args:
            current_node: Current node being visited.
            result: List to store the nodes in post-order order.
        """
        if current_node is not None:
            self._post_order_traversal_recursive(current_node.left, result)
            self._post_order_traversal_recursive(current_node.right, result)
            result.append(current_node.data)

    def _display(self):
        """
        Returns a string representation of the binary search tree.

        Returns:
            String representation of the binary search tree.
        """
        if self.root is None:
            return "Empty Binary Search Tree"

        lines, *_ = self._display_helper(self.root)
        return "\n".join(lines)

    def _display_helper(self, node):
        """
        Helper method to construct the string representation of the binary search tree.

        Args:
            node: Current node being visited.

        Returns:
            Lines representing the binary search tree, along with the width, height, and middle index.
        """
        if node.right is None and node.left is None:
            line = str(node)
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle

        if node.right is None:
            lines, n, p, x = self._display_helper(node.left)
            s = str(node)
            u = len(s)
            first_line = (x + 1) * " " + (n - x - 1) * "_" + s
            second_line = x * " " + "/" + (n - x - 1 + u) * " "
            shifted_lines = [line + u * " " for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2

        if node.left is None:
            lines, n, p, x = self._display_helper(node.right)
            s = str(node)
            u = len(s)
            first_line = s + x * "_" + (n - x) * " "
            second_line = (u + x) * " " + "\\" + (n - x - 1) * " "
            shifted_lines = [u * " " + line for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2

        left, n, p, x = self._display_helper(node.left)
        right, m, q, y = self._display_helper(node.right)
        s = str(node)
        u = len(s)
        first_line = (x + 1) * " " + (n - x - 

1) * "_" + s + y * "_" + (m - y) * " "
        second_line = x * " " + "/" + (n - x - 1 + u + y) * " " + "\\" + (m - y - 1) * " "
        if p < q:
            left += [n * " "] * (q - p)
        elif q < p:
            right += [m * " "] * (p - q)
        zipped_lines = zip(left, right)
        lines = [first_line, second_line] + [a + u * " " + b for a, b in zipped_lines]
        return lines, n + m + u, max(p, q) + 2, n + u // 2


if __name__ == "__main__":
    # Create a new binary search tree
    bst = BinarySearchTree()

    # Insert nodes into the binary search tree
    bst.insert(5)
    bst.insert(3)
    bst.insert(7)
    bst.insert(2)
    bst.insert(4)
    bst.insert(6)
    bst.insert(8)

    # Print the binary search tree structure
    print("Binary Search Tree Structure:")
    print(bst)
    # Output:
    # Binary Search Tree Structure:
    #            __________Node(5)__________
    #           /                           \
    #     ___Node(3)___               ___Node(7)___
    #    /             \             /             \
    # Node(2)       Node(4)       Node(6)       Node(8)

    # Perform in-order traversal
    in_order = bst.in_order_traversal()
    print("In-Order Traversal:", in_order)
    # Output:
    # In-Order Traversal: [2, 3, 4, 5, 6, 7, 8]

    # Perform pre-order traversal
    pre_order = bst.pre_order_traversal()
    print("Pre-Order Traversal:", pre_order)
    # Output:
    # Pre-Order Traversal: [5, 3, 2, 4, 7, 6, 8]

    # Perform post-order traversal
    post_order = bst.post_order_traversal()
    print("Post-Order Traversal:", post_order)
    # Output:
    # Post-Order Traversal: [2, 4, 3, 6, 8, 7, 5]

    # Get the size of the binary search tree
    tree_size = bst.size()
    print("Binary Search Tree Size:", tree_size)
    # Output:
    # Binary Search Tree Size: 7

    # Get the height of the binary search tree
    tree_height = bst.height()
    print("Binary Search Tree Height:", tree_height)
    # Output:
    # Binary Search Tree Height: 2

    # Search for a node in the binary search tree
    node_to_search = 6
    found = bst.search(node_to_search)
    print(f"Node {node_to_search} Found:", found)
    # Output:
    # Node 6 Found: True

    # Delete a node from the binary search tree
    node_to_delete = 4
    bst.delete(node_to_delete)

    # Print the binary search tree structure after deletion
    print(f"Binary Search Tree Structure after deleting node {node_to_delete}:")
    print(bst)
    # Output:
    # Binary Search Tree Structure after deleting node 4:
    #            ___Node(5)__________
    #           /                    \
    #     ___Node(3)           ___Node(7)___
    #    /                    /             \
    # Node(2)              Node(6)       Node(8)
